class Solution {
public:
    vector<int> f;
    int find(int x){
        return x == f[x] ? x : find(f[x]);
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        f[y] = x;
    }
    
    vector<int> pondSizes(vector<vector<int>>& land) {
        int m = land.size();
        int n = land[0].size();
        f.resize(m*n);
        
        for(int i = 0;i < m*n;i++){
            f[i] = i;
        }

        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(land[i][j] != 0){
                    f[i*n+j] = -1;
                    continue;
                }
                
                if(j > 0 && land[i][j-1] == 0){
                    Union(i*n+j-1,i*n+j);
                }
                if(i > 0 && j > 0 && land[i-1][j-1] == 0){
                    Union((i-1)*n+j-1,i*n+j);
                }
                if(i > 0 && land[i-1][j] == 0){
                    Union((i-1)*n+j,i*n+j);
                }
                if(i > 0 && j < n - 1 && land[i-1][j+1] == 0){
                    Union((i-1)*n+j+1,i*n+j);
                }
            }
        }
        
        unordered_map<int,int> ump;
        for(int i = 0;i < m*n;i++){
            if(f[i] != -1){
                int x = find(f[i]);
                ump[x]++;
            }
        }
        vector<int> ret;
        for(auto& kv : ump){
            ret.push_back(kv.second);
        }
        sort(ret.begin(),ret.end());
        return ret;
    }
};
